496D - Tennis Game - CodeForces Solution

#include "bits/stdc++.h"
using namespace std;

void solve()
{
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int i = 0, in; i < n; ++i)
        cin >> in, a[i] = (in == 1), b[i] = (in == 2);
    for (int i = 1; i < n; ++i)
        a[i] += a[i - 1], b[i] += b[i - 1];
    vector<pair<int, int>> ans;
    auto solve = [&](int &l, int r, int i)
    {
        int lo = l, hi = r, ret = -2;
        while(lo <= hi)
        {
            int md = (lo + hi) >> 1;
            int p1 = a[md] - (l ? a[l - 1] : 0), p2 = b[md] - (l ? b[l - 1] : 0);
            if(p1 >= i or p2 >= i)
                hi = md - 1, ret = md;
            else
                lo = md + 1;
        }
        int p2 = 0;
        if(ret != -1) p2 = b[ret] - (l ? b[l - 1] : 0);
        l = ret + 1;
        return (p2 == i);
    };

    for(int i = 1; i <= max(a[n - 1], b[n - 1]); ++i)
    {
        bool flag = true;
        int l = 0, p1 = 0, p2 = 0;
        while(l < n)
        {
            int mx = 2 * i - 1, r = min(l + mx - 1, n - 1);
            int ret = solve(l, r, i);
            p1 += (ret == 0), p2 += (ret == 1);
            if(l == -1)
            {
                flag = false;
                break;
            }
        }
        if(p1 == p2) flag = false;
        int mx = max(p1, p2);
        l = 0, p1 = 0, p2 = 0;
        while(l < n)
        {
            if(p1 == mx or p2 == mx)
            {
                flag = false;
                break;
            }
            int mx = 2 * i - 1, r = min(l + mx - 1, n - 1);
            int ret = solve(l, r, i);
            p1 += (ret == 0), p2 += (ret == 1);
            if(l == -1)
            {
                flag = false;
                break;
            }
        }
        if(flag)
            ans.emplace_back(max(p1, p2), i);
    }

    sort(ans.begin(), ans.end());

    cout << ans.size() << '\n';
    for(auto &[t, s] : ans)
        cout << t << ' ' << s << '\n';
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int tc = 1;
    // cin >> tc;
    for (int i = 1; i <= tc; ++i)
        solve();
}